package com.company.Sort2;

import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}14:47
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {1,5,20,6,48,15,100};
        Radix(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void Radix(int[] arr){
        //首先找到最大的数确定最大的位数
        int max = arr[0];
        for (int i = 0;i < arr.length - 1; i++){
            max = (max < arr[i+1]) ? arr[i+1] : max;
        }
        int len = (max+"").length();//最大的位数
        //定义桶
        int[][] RadixElement = new int[10][arr.length];
        //桶的容量数组
        int[] RadixIndex = new int[10];

        for (int i = 0,n = 1; i < len; i++,n*=10){//每位数依次循环
            //获取每位数的对应的值
            for (int j = 0; j < arr.length; j++){
                int index = arr[j]/n%10;
                RadixElement[index][RadixIndex[index]] = arr[j];
                RadixIndex[index]++;
            }

            //将每个桶的数组还原
            int index = 0;
            for (int x = 0; x < 10; x++){
                if (RadixIndex[x] != 0){
                    for (int l = 0;l < RadixIndex[x];l++){
                        arr[index] = RadixElement[x][l];
                        index++;
                    }
                }
                RadixIndex[x] = 0;
            }
        }
    }

}
